With an increase in popularity of Internet communications, the Internet infrastructure has expanded significantly. Inter-network relay units, such as bridges and routers, have been used to couple different segments of the Internet infrastructure. Bridges perform packet transfer processes for each destination using a data link layer and routers do the same using a network layer. A network infrastructure configured from conventional relay units uses statistical multiplexing and is easy to access. However, such a network infrastructure does not enable end-to-end bandwidth guarantees.
In recent years, a virtual private network (VPN) has been devised that uses Internet technology. According to this concept, a user may construct a closed user group (CUG) on a public network to establish a private network. FIG. 16 illustrates an example of a conventional VPN 16000. In the VPN 16000, the user may transmit a packet to a destination through a core network 16010. Each packet is transmitted through the core network 16010 by a relay unit 16020 coupled to a multiple access line 16050, such as a trunk line. Each multiple access line 16050 may support multiple tunnels 16060, where each tunnel 16060 is a multiplexed communication link. The relay unit 16020 determines a destination relay unit 16030–16040 for the packet and selects a tunnel 16060 to route the packet through the selected tunnel 16060 to the destination relay unit 16030–16040 through the selected tunnel 16060.
In general, a VPN 16000 service provider may guarantee a minimum allocated bandwidth to the user. With guaranteed minimum bandwidth service, the user can contract to always have the guaranteed bandwidth available for their exclusive use. Therefore, the user can be guaranteed at least the minimum rate of communication between endpoints of the VPN without interruption, even when the public network is congested with other traffic. Furthermore, the user can use additional bandwidth when the public network is not congested with other traffic and additional bandwidth is available. However, VPN 16000 service providers have not made guaranteed minimum bandwidth service available using the Internet.
For example, a frame relay network may guarantee a bandwidth at a committed information rate (CIR), even when the frame relay network is congested. Each user of the frame relay network may contract for secure a guaranteed minimum bandwidth in the following manner. Initially, a CIR value corresponding to the guaranteed minimum bandwidth is set up for the user's access line at an entrance to the frame relay network. When a packet is received exceeding the CIR value, the packet is marked for preferential discard. The marked packet is preferentially discarded when the network is congested. According to this method, when the network is not congested and additional bandwidth is available, each packet marked for preferential discard can be relayed. Therefore, the contracting user can efficiently use any additional network bandwidth that is available.
In the VPN 16000, packets processed by different applications are transferred from access lines of one or more users. The priority of packets produced may vary significantly according to the application that produced the packets. For example, packets produced by applications used for e-mail or web access may have a relatively low priority, whereas packets produced by applications used for real time voice/video communication or a mission critical system may have a relatively high relay priority.
However, conventional minimum bandwidth guarantee methods, such as frame relay, do not consider the relay priority for individual packets when selecting packets to be marked for preferential discard. Consequently, the user's high priority packets, that should be relayed, may be discarded while the user's low priority packets are relayed through the network. Therefore, the user's guaranteed minimum bandwidth is not optimally allocated.
There are other guaranteed minimum bandwidth methods that do consider the relay priority of individual packets. However, in those methods a fixed amount of bandwidth is allocated for guaranteed traffic and best-effort traffic for each output link, such as each tunnel 16060. Therefore, packets may be discarded without consideration of their relay priority when the number of packets at a priority level directed to the output link exceeds the allocated bandwidth for that priority level. FIG. 17 illustrates an example of a conventional method for guaranteeing a minimum bandwidth based on relay priority. For example, a medium/high priority packet may be allocated with guaranteed traffic, such as committed data rate (CDR) traffic, and a low priority packet may be allocated with best-effort traffic to be marked for preferential discard. In this example, high priority packets may be discarded when the traffic exceeds the CDR, even though the volume of low priority traffic is less than the bandwidth allocated for low priority traffic.
Another packet transfer scheduling method uses a token bucket to police (i.e., check rate conformance) and shape traffic based on the guaranteed minimum bandwidth. In the token bucket method, each token represents a data transfer unit such as a bit or byte. Each bucket fills with tokens at a rate based on the guaranteed minimum bandwidth, and approval to transfer packets is determined by the quantity of tokens in the bucket.
When the quantity of tokens in the bucket exceeds a packet size, approval is given to transfer the packet and a number of tokens equivalent to the packet size are deducted from the quantity of tokens in the bucket. Otherwise, when the quantity of tokens is less than the packet size, approval to transfer the packet may be withheld until the quantity of tokens in the bucket exceeds the packet size. However, even when the quantity of tokens in the bucket is insufficient, the packet may be transferred after attaching a mark indicating traffic in excess of the guaranteed minimum bandwidth. The supply of packets to be transferred may be limited; therefore the supply of tokens to the bucket may be stopped when the quantity of tokens reaches this limited value because the traffic rate may be less than the minimum guaranteed bandwidth for a long period of time, such as an hour.
In the token bucket scheduling method, it is possible to approve the transfer of a traffic burst within the range of token bucket capacity based on the guaranteed minimum bandwidth. A system for realizing this burst transfer would comprise counter logic for filling a token bucket at a defined rate, a token counter for each bucket provided for each buffer or queue, and computational logic for deducting tokens from the counter of each bucket according to the size of each transferred packet, etc.
However, in such a system, smaller token units require faster computational logic for deducting tokens from the counter of each bucket. Further, when there are a plurality of queues, a mechanism for supplying tokens at a rate based on each guaranteed minimum bandwidth and a mechanism for counting tokens for each queue are required. Such a system would be complicated and large in size.
For each user, relay priority is a matter of relative preference. Accordingly, in order to use a guaranteed bandwidth efficiently, it is desirable that packets with low relay priority should be transferred up to the guaranteed minimum bandwidth unless there is another packet having higher relay priority at the same time. Furthermore, packets having higher relay priority should be preferentially allocated as traffic within the guaranteed minimum bandwidth without being affected by another packet having lower relay priority. If packets having high relay priority are received in excess of the guaranteed minimum bandwidth, the high relay priority packets should be treated as a best-effort traffic and may be marked for preferential discard, even though the relay priority is high.